#include <stdio.h>
#include <stdlib.h>
#include <string.h> // memset的原型定义在<string.h>中

//\****************************************************************************************************\//
/**
 * 统计数字
 * 生成N个0到N的整数，统计每个数出现的次数
 */

// 数组拷贝
static void array_copy(int *src, int src_len, int *dest, int dest_len)
{
    for (int i = 0; i < src_len && i < dest_len; i++)
    {
        *(dest++) = *(src++);
    }
}
// 生成N个0到N的整数
static int *generate_random(int *arr, int N)
{
    printf("generate positive integers up to %d\n", N);
    for (int i = 0; i < N; i++)
    {
        arr[i] = rand() % N;
    }
    return arr;
}
// 打印数组内容
static void print_random(int *arr, int N)
{
    for (int i = 0; i < N; i++)
    {
        printf("%-3d ", arr[i]);
    }
    printf("\n");
}
// 统计数组中每个数字有多少个
static int count_random(int *arr, int N, int val)
{
    int count = 0;
    for (int i = 0; i < N; i++)
    {
        if (arr[i] == val)
        {
            ++count;
        }
    }
    return count;
}
static int compare_func(const void *a, const void *b)
{
    return *(int *)a - *(int *)b;
}
static void sort_array(int *arr, int N)
{
    qsort(arr, N, sizeof(int), compare_func);
}
// 打印数组下标
static void print_arr_i(int *a, int len)
{
    for (int i = 0; i < len; i++)
    {
        printf("%-3d ", i);
    }
    printf("\n");
}
static int max(int a, int b)
{
    return a > b ? a : b;
}
// 分隔符
static char *gen_spilt(char ch, size_t n)
{
    size_t per_num_len = n;
    char *str = calloc(per_num_len, sizeof(char));
    memset(str, '-', per_num_len - 1);
    str[per_num_len] = '\0';
    return str;
}
// 打印二维数组
static void print_arr_two(int c, int r, int a[c][r], int N)
{
    size_t per_num_len = 3 * r + 1;
    char *str = gen_spilt('-', per_num_len);
    printf("%s\n", str);
    for (int i = 0; i < c; i++)
    {
        // printf("%s\n", str);
        for (int j = 0; j < r; j++)
        {
            int x = a[i][j];
            if (x < 0)
            {
                printf("   ");
            }
            else if (x >= 0 && x <= N)
            {
                if (x == 42) // * 字符ascii
                {
                    // if (i == 0 || j == 0) // 第0行或第0列为统计的数字 其他的为*字符
                    if ((i == 42 && j == 0) || (i == 0 && j == 42)) // 只有第42行第0列和第0行第42列的42为数字
                        printf("%-3d", x);
                    else
                        printf("%-3c", x);
                }
                else
                {
                    printf("%-3d", x);
                }
            }
            else if (x > N)
            {
                printf("%-3c", x);
            }
        }
        printf("|\n");
    }
    printf("%s\n", str);
}
// 排序后的数组 统计并打印统计表
static void print_sorted_random(int *arr, int N)
{
    printf("number statistics\n");
    int *tmp = calloc(N, sizeof(int)); // 分配并初始化为 0
    // memset(tmp, 0, N * sizeof(int));  // 初始化为 0
    int m = 0;
    for (int i = 0; i < N; i++)
    {
        int count = count_random(arr, N, arr[i]); // 计数
        m = max(m, count);
        tmp[arr[i]] = count;
    }
    print_random(tmp, N);
    print_arr_i(tmp, N);
    printf("two-dimensional array\n");
    int a[N][m + 1];
    int b[m + 1][N];
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j <= m; j++)
        {
            if (j == 0)
            {
                a[i][0] = i;
                b[0][i] = i;
            }
            else if (j > 0 && j <= tmp[i])
            {
                a[i][j] = '*';
                b[j][i] = '*';
            }
            else if (j > tmp[i])
            {
                a[i][j] = -1;
                b[j][i] = -1;
            }
        }
    }
    print_arr_two(N, m + 1, a, N);
    print_arr_two(m + 1, N, b, N);
}
// 排序、去重、统计
void test_base_001()
{
    printf("^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n");
    printf("| Count the number of occurrences |\n");
    printf("^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n");
    printf("Generate N random positive integers from 0 to N\n");
    printf("Count how many times each number appears\n");
    printf("Enter a negative number to exit\n");
    printf("For example\n");
    printf("------------------------------------------------------------\n");
    printf("|0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 |\n");
    printf("|*  *  *     *  *     *     *     *        *  *  *     *     |\n");
    printf("|   *  *     *  *     *                                *     |\n");
    printf("|   *                 *                                      |\n");
    printf("------------------------------------------------------------\n");
    printf("\n");
    while (1)
    {
        // 生成随机数
        printf("Input a number N(0 < N <= 1000) to randomly generate N positive integers from 0 to N : ");
        int N;
        scanf("%d", &N);
        if (N < 0)
        {
            printf("game over!\n");
            break;
        }
        int times;
        // input_times:
        //     printf("Input number of games: ");
        //     scanf("%d", &times);
        //     if (times < 0 || times > 10)
        //     {
        //         printf("The times is between 1 and 10\n");
        //         goto input_times;
        //     }
        printf("If times is less than 0 or greater than 10, times is equal to 1, Input number of games: ");
        scanf("%d", &times);
        if (times < 0 || times > 10)
        {
            printf("The times is between 1 and 10\n");
            times = 1;
        }
        int init_times = times;
        while (times--)
        {
            printf("times %d start...\n", init_times - times);
            int *arr = malloc(sizeof(int) * N);
            memset(arr, 0, N * sizeof(int)); // 初始化为 0 memset的原型定义在<string.h>中
            generate_random(arr, N);
            // 打印数组
            print_random(arr, N);

            // 排序
            sort_array(arr, N);
            print_random(arr, N);
            // 统计排序后的数据
            print_sorted_random(arr, N);
            printf("\n");
        }
    }
}
//\****************************************************************************************************\//
/**
 * 一元钱兑换方案
 * 如果要将栈整钱换成零钱，那么一元钱可兑换成一角、两角或五角，问有哪些兑换方案
 */

void test_base_002()
{
    printf("^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n");
    printf("| One yuan exchange scheme |\n");
    printf("^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n");
    for (int i = 0; i <= 10; i++)
    {
        for (int j = 0; j <= 5; j++)
        {
            for (int k = 0; k <= 2; k++)
            {
                if (i + j * 2 + k * 5 == 10)
                {
                    printf("Scheme %d : A corner %d, Two angles %d, The Pentagon %d\n", i, j, k);
                }
            }
        }
    }
}
//\****************************************************************************************************\//
/**
 * 连续重复出现数字的最大计数
 * 删除多余的重复元素
 */

void test_base_003()
{
    printf("^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n");
    printf("| The maximum count of consecutive recurring digits |\n");
    printf("^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n");
    printf("Enter a negative number to exit\n");
    while (1)
    {
        // The maximum count of consecutive recurring digits
        printf("Input a number N to generate N random numbers[0,N): ");
        int N;
        scanf("%d", &N);
        if (N < 0)
        {
            printf("game over!\n");
            break;
        }
        int *arr = calloc(N, sizeof(int));
        generate_random(arr, N);
        print_random(arr, N);

        // int *arr = malloc(sizeof(int) * N);
        // memset(arr, 0, N * sizeof(int)); // 初始化为 0 memset的原型定义在<string.h>中
        // generate_random(arr, N);
        // // 打印数组
        // print_random(arr, N);

        // eg.
        // 1 1 1 4 5
        // 0 1 2 3 4 i j d
        int pre = 1, k = 0;     // 用于统计最大计数以及下标
        int new_len = N, d = 0; // 用于删除重复元素
        int *tmp = calloc(N, sizeof(int));
        array_copy(arr, N, tmp, N);
        // printf("Temporary array -> ");
        // print_random(tmp, N);
        for (int i = 0, j = 1; i < N; i++, j++)
        {
            int c = 1; // 保存连续出现的数字的计数
            while (j <= N - 1 && arr[i] == arr[j])
            {
                i = j;
                j++;
                c++;
            }

            // 删除多余的重复元素
            tmp[++d] = tmp[j];         // 不能在原数组上删除 因为后面还要计算最大计数的下标，原数组删除后元素会变动
            new_len = new_len + 1 - c; // 删除重复元素后的数组有效元素长度

            if (c > pre)
            {
                k = i; // 每次出现的最大计数的数字下标
                pre = c;
            }
            // pre = max(pre, c); // 连续重复数字的最大计数
        }
        if (pre == 1)
        {
            printf("There were no consecutive repeated numbers\n"); // 没有出现连续重复的数字
            continue;
        }
        // 比较截断后的原数组与临时数组
        // printf("truncation Original array  -> ");
        print_random(arr, new_len);
        // printf("truncation Temporary array -> ");
        print_random(tmp, new_len);
        printf("The maximum count and number of consecutive repeated digits are: %d -> %d\n", arr[k], pre);
    }
}
//\****************************************************************************************************\//

// 判断是否质数
static int isPrime(const int num)
{
    if (num <= 1)
    {
        return 0;
    }
    for (int i = 2; i * i < num; i++)
    {
        if (num % i == 0)
        {
            return 0;
        }
    }
    return 1;
}

// 判断是否回文数
static int isPalindrome(int num)
{
    int original = num, reversed = 0;
    while (num > 0)
    {
        reversed = reversed * 10 + num % 10;
        num /= 10;
    }
    return original == reversed;
}
//\****************************************************************************************************\//

void menu()
{
    printf("-----------------------------------------------------------------------\n");
    printf("|                                 menu                                |\n");
    printf("|                                                                     |\n");
    printf("|                                                                     |\n");
    printf("| 1. One yuan exchange scheme                                         |\n");
    printf("| 2. The maximum count of consecutive recurring digits                |\n");
    printf("| 3. Count the number of occurrences                                  |\n");
    printf("|                                                                     |\n");
    printf("|                                                                     |\n");
    printf("-----------------------------------------------------------------------\n");
    printf("\n");
}
void test_base()
{
    int flag = 1;
    while (flag)
    {
        menu();

        printf("Enter a negative number to exit\n");
        printf("Enter the program you want to select: ");
        int select;
        scanf("%d", &select);

        if (select < 0)
        {
            flag = 0;
            continue;
        }

        switch (select)
        {
        case 1:
            test_base_002(); // 1 One yuan exchange scheme
            break;
        case 2:
            test_base_003(); // 2 The maximum count of consecutive recurring digits
            break;
        case 3:
            test_base_001(); // 3 Count the number of occurrences
            break;
        default:
            printf("Typo, please retype\n");
            break;
        }
        system("pause");
        system("cls");
    }
    printf("Thanks for the experience\n");
    system("pause");
}